package com.kongge.algorithm.demo;

import com.kongge.algorithm.list.ListNode;

/**
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的结点依然是按照递增排序的。
 * @author gaoshiqi
 *
 */
public class MergeSortList implements IAlgorithm {

	public void execute() {
		ListNode<Integer> listOne = ListNode.createList(1, 3, 5);
		ListNode<Integer> listTwo = ListNode.createList(2, 4, 6);
		ListNode<Integer> newList = mergeList(listOne, listTwo);
		ListNode.printList(newList);
	}

	private ListNode<Integer> mergeList(ListNode<Integer> listOne, ListNode<Integer> listTwo) {
		ListNode<Integer> newHead = null;
		ListNode<Integer> newTail = null;
		ListNode<Integer> nextNode = null;
		while (listOne != null || listTwo != null) {
			if (listOne == null) {
				nextNode = listTwo;
				listTwo = listTwo.next;
			} else if (listTwo == null) {
				nextNode = listOne;
				listOne = listOne.next;
			} else {
				if (listOne.t < listTwo.t) {
					nextNode = listOne;
					listOne = listOne.next;
				} else {
					nextNode = listTwo;
					listTwo = listTwo.next;
				}
			}
			if (newHead == null) {
				newHead = nextNode;
				newTail = nextNode;
			} else {
				newTail.next = nextNode;
				newTail = newTail.next;
			}
		}
		return newHead;
	}
	
}
